%==============================================================================
%PREDICADOS AUXILIARES
%==============================================================================

%entre(+X, +Y, -Z)
entre(X, Y, X) :- X =< Y.
entre(X, Y, Z) :- X < Y, N is X+1, entre(N, Y, Z).

%infinitos(N, I)
infinitos(N, N).
infinitos(N, I) :- Y is I+1, infinitos(N, Y).

%cadenasDeLongitudN(+N, -L)
cadenasDeLongitudN(0, []).
cadenasDeLongitudN(N, [X|L]) :- N > 0, entre(0, 1, X), Nm1 is N - 1, cadenasDeLongitudN(Nm1, L).

%sacarElementoDePosicion(+L, +P, -L)
%exSacarElementoDePosicion([_|XS], 0, YS) :- XS = YS.
%exSacarElementoDePosicion([X|XS], N, [Y|YS]) :- N > 0, X = Y, Nm1 is N - 1, sacarElementoDePosicion(XS, Nm1, YS).

sacarElementoDePosicion(XS, N, YS) :- length(XS, LongXS), M is LongXS - N -1, length(Prefijo, N), length(Sufijo, M), 
									  append(Prefijo,_,XS), append(_,Sufijo,XS), append(Prefijo, Sufijo, YS).

%agregarElementoDePosicion(+L, +P, -L)
%exAgregarElementoEnPosicion(XS, 0, E, YS) :- [E|XS] = YS.
%exAgregarElementoEnPosicion([X|XS], N, E, [Y|YS]) :- N > 0, X = Y, Nm1 is N - 1, agregarElementoEnPosicion(XS, Nm1, E, YS).

agregarElementoEnPosicion(XS, N, E, YS) :- length(XS, LongXS), M is LongXS - N, length(Prefijo, N), length(Sufijo, M), 
									  append(Prefijo,_,XS), append(_,Sufijo,XS), append(Prefijo, [E|Sufijo], YS).

%cambiarElementoDePosicion(+L, +P, -L)
%exCambiarElementoDePosicion([_|XS], 0, E, YS) :- [E|XS] = YS.
%exCambiarElementoDePosicion([X|XS], N, E, [Y|YS]) :- N > 0, X = Y, Nm1 is N - 1, cambiarElementoDePosicion(XS, Nm1, E, YS).

cambiarElementoDePosicion(XS, N, E, YS) :- sacarElementoDePosicion(XS,N,ZS), agregarElementoEnPosicion(ZS,N,E,YS).

complemento(E, S) :- S is abs(E - 1).

%elementoDePosicion(+L, +P, -L)
%exElementoDePosicion([X|_], 0, E) :- E = X. 
%exElementoDePosicion([_|XS], N, E) :- N > 0, Nm1 is N - 1, elementoDePosicion(XS, Nm1, E).

elementoDePosicion(XS,N,E) :- length(XS, LongXS), M is LongXS - N -1, length(Prefijo, N), length(Sufijo, M), 
							  append(Prefijo,_,XS), append(_,Sufijo,XS), append(Prefijo, [E|Sufijo], XS).


%caracterValido(?C)
caracterValido(C) :- entre(0, 1, C).

%cadenaValida(+C)
cadenaValida(C) :- not(atom(C)), forall(member(X, C), caracterValido(X)).

%==============================================================================

%disHam obtiene la distancia de Hamming entre dos cadenas de la misma longitud. En el caso en el que ambas cadenas estan instanciadas se
%chequea la diferencia caracter a caracter. En el caso en que solo la distancia N no se encuentra instanciada, usando el predicado "entre" se 
%define que la distancia puede estar entre 0 y la longitud de la cadena XS y se verifica cuales se corresponden con la distancia de Hamming.
%Cuando solo la cadena YS no esta instanciada, esta variable se asocia a todas las cadenas posibles (de ceros y unos) de longitud N usando el
%predicado cadenasDeLongitudN. Finalmente, cuando YS y N no estan instanciados, se instancia primero N con valores entre 0 y la longitud de XS
%y luego, en sucesivos llamados, se instanciaran las cadenas YS para cada N definido.

%distHam(+S, ?T, ?D)

distHam([], [], 0).
distHam([X|XS], [Y|YS], N) 	:- ground([Y|YS]), ground(N), caracterValido(X), caracterValido(Y), length([X|XS], L1), length([Y|YS], L2), L1 = L2, 
								M is N - abs(X-Y), distHam(XS, YS, M).
distHam(XS, YS, N) 			:- not(ground(YS)), ground(N), N >= 0, length(XS, Long), N =< Long, cadenasDeLongitudN(Long, YS), 
								distHam(XS, YS, N).
distHam(XS, YS, N) 			:- not(ground(N)), length(XS, Long), entre(0, Long, N), distHam(XS, YS, N).


%distPref(+S, ?T, ?D)
distPref([], [], 0).
distPref([X|XS], [Y|YS], N) :- ground(N), ground([Y|YS]), cadenaValida([X|XS]), cadenaValida([Y|YS]), Y = X, distPref(XS,YS,N).
distPref([X|XS], [X|YS], N) :- distPref(XS,YS,N)
distPref([X|XS], [], N) 	:- ground(N), cadenaValida([X|XS]), length([X|XS], Long), N = Long.
distPref([], [Y|YS], N) 	:- ground(N), ground([Y|YS]), cadenaValida([Y|YS]), length([Y|YS], Long), N = Long.

distPref([X|XS], [Y|YS], N) :- ground(N), ground([Y|YS]), cadenaValida([X|XS]), cadenaValida([Y|YS]),
									 X \= Y, length([X|XS], LongX), length([Y|YS], LongY), SumLong is LongX + LongY, N = SumLong.
distPref(XS, YS, N) 		:- ground(N), not(ground(YS)), length(XS, LongXS), LongMin is max(LongXS - N, 0), LongMax is LongXS + N,
									entre(LongMin, LongMax, Long), cadenasDeLongitudN(Long, YS), distPref(XS, YS, N).
distPref(XS, YS, N) 		:- not(ground(N)), ground(YS), length(XS, LongX), length(YS, LongY), SumLong is LongX + LongY, entre(0, SumLong, N), 
									distPref(XS,YS, N).									 
distPref(XS, YS, N) 		:- not(ground(N)), not(ground(YS)), cadenaValida(XS), length(YS,0), infinitos(N, 0), distPref(XS, YS, N).
distPref(XS, YS, N) 		:- not(ground(N)), not(ground(YS)), cadenaValida(XS), length(YS, LongYS), LongYS > 0, length(XS, LongXS), 
									SumLong is LongXS + LongYS,	entre(0, SumLong, N), distPref(XS,YS, N).


%distPref(XS, XS, 0).
%distPref([X|XS], [X|YS], N) :- distPref(XS,YS,N).
%distPref([X|XS], [], N) :- M is N + 1, cadenaValida([X|XS]), distPref(XS, [], M).
%distPref([], [Y|YS], N) :- M is N + 1, cadenaValida([Y|YS]), distPref([], YS, M).
%distPref([X|XS], [Y|YS], N) :- not(Y = X), length([Y|YS], LongYS), length([X|XS], LongXS), N is LongXS + LongYS.

%distEd(+S, ?T, ?D)
distEd(XS, YS, 0) :- ground(YS), cadenaValida(XS), cadenaValida(YS), XS = YS.
distEd(XS, YS, N) :- ground(YS), ground(N), cadenaValida(XS), cadenaValida(YS), N > 0, length(YS, LongY), entre(0, LongY, Pos), 
							sacarElementoDePosicion(YS, Pos, ZS), Nm1 is N-1, distEd(XS, ZS, Nm1).
distEd(XS, YS, N) :- ground(YS), ground(N), cadenaValida(XS), cadenaValida(YS), N > 0, length(YS, LongY), entre(0, LongY, Pos), 
							entre(0, 1, E),	agregarElementoEnPosicion(YS, Pos, E, ZS), Nm1 is N-1, distEd(XS, ZS, Nm1).
distEd(XS, YS, N) :- ground(YS), ground(N), cadenaValida(XS), cadenaValida(YS), N > 0, length(YS, LongY), entre(0, LongY, Pos), 
							elementoDePosicion(YS, Pos, E), complemento(E, CompE), cambiarElementoDePosicion(YS, Pos, CompE, ZS), 
							Nm1 is N-1, distEd(XS, ZS, Nm1).
distEd(XS, YS, N) :- ground(YS), not(ground(N)), cadenaValida(XS), cadenaValida(YS), length(XS, LongXS), entre(0, LongXS, N), 
							distEd(XS, YS, N), !.
distEd(XS, YS, N) :- not(ground(YS)), ground(N), cadenaValida(XS), setof(ZS, (length(XS, LongXS), MinLong is max(0, LongXS - N), 
							MaxLong is LongXS + N, entre(MinLong, MaxLong, Long), cadenasDeLongitudN(Long, ZS), distEd(XS, ZS, N)), SinRep), 
							member(YS, SinRep).
distEd(XS, YS, N) :- not(ground(YS)), not(ground(N)), cadenaValida(XS), length(YS,0), infinitos(N, 0), distEd(XS, YS, N).
distEd(XS, YS, N) :- not(ground(YS)), not(ground(N)), cadenaValida(XS), length(YS, LongYS), LongYS > 0, length(XS, LongXS), 
							entre(0, LongXS, N), distEd(XS, YS, N).
